#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=1e5+5;
int n,q,rt1[N],rt2[N];
struct Seg{
	int l,r;
}a[N];
vector<int> ins[N];
struct SegmentTree{
	struct Node{
		int ls,rs,cnt;
		ll suml,sumr;
	}t[N*25];
	int tot;
	int clone(int p){
		t[++tot]=t[p];
		return tot;
	}
	void insert(int pos,int i,int& p,int L=1,int R=n){
		p=clone(p);
		++t[p].cnt;
		t[p].suml+=a[i].l;
		t[p].sumr+=a[i].r;
		if(L==R) return;
		int mid=(L+R)/2;
		if(pos<=mid){
			insert(pos,i,t[p].ls,L,mid);
		}else{
			insert(pos,i,t[p].rs,mid+1,R);
		}
	}
	ll query(int l,int r,ll w1,int w2,int w3,int p,int L=1,int R=n){
		if(!p||l>R||r<L){
			return 0;
		}
		if(l<=L&&R<=r){
			return w1*t[p].cnt+w2*t[p].suml+w3*t[p].sumr;
		}
		int mid=(L+R)/2;
		return query(l,r,w1,w2,w3,t[p].ls,L,mid)+query(l,r,w1,w2,w3,t[p].rs,mid+1,R);
	}
}seg,rseg;
struct Info{
	int i,l,r;
};
ll f[N];
ll calc(int l,int r){
	if(l>=r) return 1e18;
	ll cost=f[l]+seg.query(l,n,r-l,1,-1,rt1[r]);
	cost+=rseg.query(1,l,1,0,0,rt2[r]);
	int mid=(l+r)/2;
	cost+=seg.query(1,l-1,-l-r,0,2,rt1[mid])-seg.query(1,l-1,-l,0,1,rt1[l]);
	cost+=seg.query(1,l-1,r,0,-1,rt1[r]);
	cost+=rseg.query(l,mid,-l,1,0,rt2[r+1]);
	cost+=rseg.query(mid+1,r,r,-1,0,rt2[r+1]);
	return cost;
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	assert(freopen("block.in","r",stdin));
	assert(freopen("block.out","w",stdout));
	cin>>n>>q;
	For(i,1,q){
		cin>>a[i].l>>a[i].r;
		ins[a[i].r].push_back(i);
	}
	For(i,1,n){
		rt1[i]=rt1[i-1];
		for(int j:ins[i]){
			seg.insert(a[j].l,j,rt1[i]);
		}
	}
	Dec(i,n,1){
		rt2[i]=rt2[i+1];
		for(int j:ins[i]){
			rseg.insert(a[j].l,j,rt2[i]);
		}
	}
	deque<Info> dq;
	memset(f,0x3f,sizeof(f));
	f[1]=0;
	dq.push_back({1,1,n});
	For(i,2,n){
		while(dq[0].r<i){
			dq.pop_front();
		}
		f[i]=calc(dq[0].i,i);
		while(dq.size()){
			auto& [j,l,r]=dq.back();
			if(calc(j,l)>calc(i,l)){
				dq.pop_back();
				continue;
			}
			int L=l,R=r;
			while(L<R){
				int mid=(L+R+1)/2;
				if(calc(j,mid)>calc(i,mid)){
					R=mid-1;
				}else{
					L=mid;
				}
			}
			r=L;
			break;
		}
		int l=(dq.size()?dq.back().r+1:1);
		if(l<=n){
			dq.push_back({i,l,n});
		}
	}
	cout<<f[n]<<'\n';
	return 0;
}